//
// Created by Administrator on 2021/8/18.
//
//可以用字符串表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：
//'A'：Absent，缺勤
//'L'：Late，迟到
//'P'：Present，到场
//如果学生能够 同时 满足下面两个条件，则可以获得出勤奖励：
//
//按 总出勤 计，学生缺勤（'A'）严格 少于两天。
//学生 不会 存在 连续 3 天或 连续 3 天以上的迟到（'L'）记录。
//给你一个整数 n ，表示出勤记录的长度（次数）。请你返回记录长度为 n 时，可能获得出勤奖励的记录情况 数量 。答案可能很大，所以返回对 109 + 7 取余 的结果。
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/student-attendance-record-ii
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <climits>
#include <string.h>

using namespace std;

class Solution {
public:
    constexpr static int MOD = 1'000'000'007;

    /**
     * 重点在于找状态
     * @param n
     * @return
     */
    int checkRecord(int n) {
        /**
         * dp
         * 状态和记录长度、缺勤次数、连续迟到天数有关
         * 缺勤次数只能是 0、1，连续迟到天数只能是0、1、2
         * 故一共六种状态
         * 转移方程：
         * 如果今天是缺勤，  dp[n][1][0] = sum(dp[n-1][0][0、1、2])
         * 如果今天是迟到    dp[n][0][1] = dp[n-1][0][0]
         *                dp[n][0][2] = dp[n-1][0][1]
         *                dp[n][1][1] = dp[n-1][1][0]
         *                dp[n][1][2] = dp[n-1][1][1]
         *           ——》 dp[n][j][k] = dp[n-1][j][k-1]
         * 如果今天是到场   dp[n][0][0] = sum(dp[n-1][0][0、1、2])
         *               dp[n][1][0] = sum(dp[n-1][1][0、1、2])
         */
        vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(2, vector<int>(3, 0)));
        dp[0][0][0] = 1; // 初始时刻 没有缺勤和迟到
        for (int i = 1; i <= n; ++i) {
            // 今天缺勤 A  dp[n][1][0] = sum(dp[n-1][0][0、1、2])
            for (int k = 0; k <= 2; ++k) {
                dp[i][1][0] = (dp[i][1][0] + dp[i - 1][0][k]) % MOD;
            }
            // 今天迟到 L
            for (int j = 0; j <= 1; ++j) {
                for (int k = 1; k <= 2; ++k) {
                    dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1]) % MOD;
                }
            }
            // 今天到场 P
            for (int j = 0; j <= 1; ++j) {
                for (int k = 0; k <= 2; ++k) {
                    dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j][k]) % MOD;
                }
            }
        }
        // 对 dp[n][j][k] 求和，就是答案
        int ans = 0;
        for (int j = 0; j <= 1; ++j) {
            for (int k = 0; k <= 2; ++k) {
                ans = (ans + dp[n][j][k]) % MOD;
            }
        }
        return ans;
    }
};

class Solution2 {
public:
    constexpr static int MOD = 1'000'000'007;

    int checkRecord(int n) {
        /**
         * dp
         * 状态和记录长度、缺勤次数、连续迟到天数有关
         * 缺勤次数只能是 0、1，连续迟到天数只能是0、1、2
         * 故一共六种状态
         * 转移方程：
         * 如果今天是缺勤，  dp[n][1][0] = sum(dp[n-1][0][0、1、2])
         * 如果今天是迟到    dp[n][0][1] = dp[n-1][0][0]
         *                dp[n][0][2] = dp[n-1][0][1]
         *                dp[n][1][1] = dp[n-1][1][0]
         *                dp[n][1][2] = dp[n-1][1][1]
         *           ——》 dp[n][j][k] = dp[n-1][j][k-1]
         * 如果今天是到场   dp[n][0][0] = sum(dp[n-1][0][0、1、2])
         *               dp[n][1][0] = sum(dp[n-1][1][0、1、2])
         * dp[n] 只和dp[n-1]有关，因此可以优化空间复杂度
         */
        int dp[2][3];
        memset(dp, 0, sizeof(dp));
//        vector<vector<int>> dp(2, vector<int>(3, 0));
        dp[0][0] = 1; // 初始时刻 没有缺勤和迟到
        for (int i = 1; i <= n; ++i) {
            int newDp[2][3];
            memset(newDp,0,sizeof(newDp));
//            vector<vector<int>> newDp(2, vector<int>(3, 0));
            // 今天缺勤 A  dp[n][1][0] = sum(dp[n-1][0][0、1、2])
            for (int k = 0; k <= 2; ++k) {
                newDp[1][0] = (newDp[1][0] + dp[0][k]) % MOD;
            }
            // 今天迟到 L
            for (int j = 0; j <= 1; ++j) {
                for (int k = 1; k <= 2; ++k) {
                    newDp[j][k] = (newDp[j][k] + dp[j][k - 1]) % MOD;
                }
            }
            // 今天到场 P
            for (int j = 0; j <= 1; ++j) {
                for (int k = 0; k <= 2; ++k) {
                    newDp[j][0] = (newDp[j][0] + dp[j][k]) % MOD;
                }
            }
            memcpy(dp, newDp, sizeof(dp));
//            dp = newDp;
        }
        // 对 dp[n][j][k] 求和，就是答案
        int ans = 0;
        for (int j = 0; j <= 1; ++j) {
            for (int k = 0; k <= 2; ++k) {
                ans = (ans + dp[j][k]) % MOD;
            }
        }
        return ans;
    }
};

using namespace std;

int main() {
    Solution2 solution;
    int number = 0;
    while (cin >> number) {
        cout << solution.checkRecord(number) << endl;
    }
    return 0;
}
